package com.zhongge.test;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 大根堆的比较规则
 */
class MaxHeap implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);//分析底层的堆的源码 可以知道只有逆着写才会为大根堆
        //具体做题的时候可以尝试切换:注意不可以直接写o2-o1 因为他们是地址，不可以直接减
        //只有调用compareTo方法 该方法里面有具体值的相减
    }
}
/**
 * @ClassName TOP_K
 * @Description TODO 解决top问题
 * @Author zhongge
 * @Date 2025/10/5 14:36
 * @Version 1.0
 */
public class TOP_K {
    public int[] smallestK(int[] arr, int k) {
        //首先在力扣中做一个安全判断 所以先定义处数组
        int[] arrTmp = new int[k];//返回k个元素 所以大小事k
        //做安全校验
        if (arr == null || k <= 0) {
            return arrTmp;
        }
        //第一步：将前k个元素创建为大根堆(自己定义比较规则)
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new MaxHeap());
        //开始将前k个构建为大根堆
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }
        //第二步：遍历后面剩下的N-K 个元素 将堆顶元素和其一一比较
        for (int i = k; i < arr.length; i++) {
            //瞄一眼堆顶元素
            int peekVal = priorityQueue.peek();
            //如果出现比堆顶小的 就删除堆顶元素 然后将其入堆
            if (arr[i] < peekVal) {
                //删除堆顶元素
                priorityQueue.poll();
                //将arr[i]入堆
                priorityQueue.offer(arr[i]);
            }
        }
        //最后一步：将剩下的堆中的元素--放入arrTmp数组并返回
        for (int i = 0; i < k; i++) {
            arrTmp[i] = priorityQueue.poll();
        }
        return arrTmp;
    }
}
